package Other;

import java.util.*;

/**
 * @author:gao
 * @date:2020/7/2
 * @time:20:11
 * @version:0.0.1
 * @description:none
 */

//public class TopKFrequent {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        solution.topKFrequent(new int[]{1,2,3,3,2},2);
//    }
//}


//数组版本的top k
//class Solution {
//    public int[] topKFrequent(int[] nums, int k) {
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int n:nums) {
//            map.put(n,map.getOrDefault(n,0)+1);
//        }
//        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return o1[1]-o2[1];
//            }
//        });
//        Object[] keySet = map.keySet().toArray();
//        for(int i=0;i<k;i++){
//            priorityQueue.add(new int[]{(Integer) keySet[i], map.get(keySet[i])});
//        }
//        int min = priorityQueue.peek()[1];
//        for(int i =k;i<keySet.length;i++){
//            int value = map.get(keySet[i]);
//            if(value>min){
//                priorityQueue.poll();
//                priorityQueue.add(new int[]{(int) keySet[i],value});
//                min = priorityQueue.peek()[1];
//            }
//        }
//        int[] ans = new int[k];
//        for(int i=0;i<k;i++){
//            ans[i]=priorityQueue.poll()[0];
//        }
//        return ans;
//    }
//}

//692. 前K个高频单词
//class Solution {
//    class Word{
//        int times;
//        String s;
//    }
//    public List<String> topKFrequent(String[] words, int k)
//    {
//        Map<String , Integer> map = new HashMap<>();
//        for (String s:words) {
//            map.put(s,map.getOrDefault(s,0)+1);
//        }
//        PriorityQueue<Word> pq = new PriorityQueue<>(new Comparator<Word>() {
//            @Override
//            public int compare(Word o1, Word o2) {
//                if(o1.times!=o2.times)return o1.times-o2.times;
//                return -o1.s.compareTo(o2.s);
//            }
//        });
//        Object[] keySet = map.keySet().toArray();
//        for(int i=0;i<k;i++){
//            Word word = new Word();
//            word.s=(String)keySet[i];
//            word.times=map.get(keySet[i]);
//            pq.add(word);
//        }
//        Word minWord = pq.peek();
//        for(int i=k;i<keySet.length;i++){
//            String curKey = (String) keySet[i];
//            int times = map.get(curKey);
//            if(minWord.times<times||(minWord.times==times&&minWord.s.compareTo(curKey)>0)){
//                pq.poll();
//                Word newWord = new Word();
//                newWord.times=times;
//                newWord.s=curKey;
//                pq.add(newWord);
//                minWord = pq.peek();
//            }
//        }
//        LinkedList<String> ans = new LinkedList<>();
//        while (!pq.isEmpty()){
//            ans.addFirst(pq.poll().s);
//        }
//        return ans;
//    }
//}